import java.util.ArrayList;
import java.util.List;

/**
 * @author : 戚欣扬
 * @Description :
 */
public class PartitionSolution {
    public static void main(String[] args) {
        SolutionOfPartition solutionOfPartition = new SolutionOfPartition();
        String test = "aab";
        List<List<String>> partition = solutionOfPartition.partition(test);
        System.out.println("partition = " + partition);
    }
}

class SolutionOfPartition {
    private List<List<String>> result = new ArrayList<>();
    private List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        partitionHelper(s);
        return result;
    }
    private void partitionHelper(String string){
        int length = string.length();
        if(length==0 || length == 1){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0 ; i<string.length();i++){
            List<String> strings = splitHelper(string, i);
            String processed = strings.get(0);
            if(!isAns(processed)) return; //剪枝操作
            path.add(processed);
            String waiting = strings.get(1);
            if(waiting.length() == 1){
                path.add(waiting);
            }
            partitionHelper(waiting);
            path.remove(path.size()-1);
        }
        return ;
    }
    private List<String> splitHelper(String s, int index){
        List<String> result = new ArrayList<>();
        if(index+1 > s.length()) {
            result.add(s);
        }
        StringBuilder tmp1 = new StringBuilder();
        StringBuilder tmp2 = new StringBuilder();
        for(int i = 0 ; i<=index;i++){
            tmp1.append(s.charAt(i));
        }
        result.add(tmp1+"");
        for (int i = index+1; i <s.length(); i++) {
            tmp2.append(s.charAt(i));
        }
        result.add(tmp2+"");
        return result;
    }

    private boolean isAns(String s){
        int left = 0;
        int right = s.length()-1;
        while(left < right){
            if(s.charAt(left)!=s.charAt(right)) return false;
        }
        return true;
    }
}

